#define _CRT_SECURE_NO_WARNINGS 1



//#include <stdio.h>
//#include <stdlib.h>
//
//struct Node
//{
//    int val;
//    struct Node *next;
//    struct Node *random;
//};
//
//struct Node* copyRandomList(struct Node* head)
//{
//    struct Node* cur = head;
//
//    //拷贝节点插入原节点的后面
//
//    while (cur)
//    {
//        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
//        copy->val = cur->val;
//
//        //插入
//        copy->next = cur->next;
//        cur->next = copy;
//
//        //迭代
//        cur = cur->next->next;
//    }
//
//    //控制拷贝节点的random
//    cur = head;
//
//    while (cur)
//    {
//        struct Node* copy = cur->next;
//        
//        if (NULL == cur->random)
//        {
//            copy->random = NULL;
//        }
//        else
//        {
//            copy->random = cur->random->next;
//        }
//
//        //迭代
//        cur = cur->next->next;
//    }
//
//    //把copy节点解下来，链接成新链表
//    struct Node* copyhead = NULL, * tail = NULL;
//    cur = head;
//
//    while (cur)
//    {
//        struct Node* copy = cur->next;
//        struct Node* next = copy->next;
//
//        //尾插
//        if (NULL == tail)
//        {
//            copyhead = tail = copy;
//        }
//        else
//        {
//            tail->next = copy;
//            tail = tail->next;
//        }
//
//        cur->next = next;
//        cur = next;
//    }
//
//    return copyhead;
//}



//#include "Stack.h"
//
//int main()
//{
//	ST s;
//	STInit(&s);
//	STPush(&s, 1);
//	STPush(&s, 2);
//	STPush(&s, 3);
//	STPush(&s, 4);
//	STPush(&s, 5);
//
//	while (!STEmpty(&s))
//	{
//		int top = STTop(&s);
//		printf("%d ", top);
//		STPop(&s);
//	}
//
//	STDestroy(&s);
//
//	return 0;
//}




#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>

typedef char STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

void STInit(ST* ps)
{
	assert(ps);

	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

void STDestroy(ST* ps)
{
	assert(ps);

	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

void STPush(ST* ps, STDataType x)
{
	assert(ps);

	if (ps->top == ps->capacity)
	{
		int newcapacity = 0 == ps->capacity ? 4 : 2 * ps->capacity;
		STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));

		if (NULL == tmp)
		{
			perror("realloc fail");
			return;
		}

		ps->a = tmp;
		ps->capacity = newcapacity;
	}

	ps->a[ps->top] = x;
	ps->top++;
}

bool STEmpty(ST* ps)
{
	assert(ps);

	return 0 == ps->top;
}

void STPop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));

	ps->top--;
}

STDataType STTop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));

	return ps->a[ps->top - 1];
}

int STSize(ST* ps)
{
	assert(ps);

	return ps->top;
}


bool isValid(char* s)
{
	ST st;
	STInit(&st);

	while (*s)
	{
		if ('[' == *s || '(' == *s || '{' == *s)
		{
			STPush(&st, *s);
		}
		else
		{
			//右括号比左括号多
			if (STEmpty(&st))
			{
				STDestroy(&st);//在返回前释放动态申请的空间，防止内存泄漏
				return false;
			}

			char top = STTop(&st);
			STPop(&st);

			//符号不匹配
			if (('[' == top && *s != ']')
				|| ('(' == top && *s != ')')
				|| ('{' == top && *s != '}'))
			{
				STDestroy(&st);//在返回前释放动态申请的空间，防止内存泄漏
				return false;
			}
		}

		++s;
	}

	//左括号比右括号多，栈不为空
	bool ret = STEmpty(&st);
	STDestroy(&st);
	return ret;
}